//基于邻接矩阵表示法的Prim算法
#include "../include/MGraph.h"
struct 
{
    int vexcode;
    int lowcost;
    bool tag;
}closest[MAX_V+1];  //定义辅助数组closest

void MinSpanningTree_Prim(MGraph G,int v)
{
    //从顶点 v 出发采用Prim算法计算图的最小生成树
    for(int j=1;j<=G.vexnum;j++)
    {
        closest[j].lowcost=G.arcs[v][j];
        closest[j].vexcode=v;
        closest[j].tag=false;
    }//初始化

    closest[v].lowcost=0;  //标记 v 已经被选中（第一个被选中的顶点）
    closest[v].tag=true;
    int k;
    for(int i=2;i<=G.vexnum;i++)//将剩余的G.vexnum-1个顶点加入到最小生成树中
    {
        int min=INFINITY;
        //第一步：在数组closest中寻找lowcost域的非零最小值
        for(int j=1;j<=G.vexnum;j++)
        {
            if(closest[j].tag==false&&closest[j].lowcost<min)
            {
                min=closest[j].lowcost;
                k=j;  //记录具有最小lowcost的元素位置
            }
        }

        //第二步：选中本轮的最小权值边对应的顶点k
        printf("边(%d,%d)权为：%d\n",k,closest[k].vexcode,min);
        closest[k].tag=true;     //标记k已经被选中

        //第三步：由于顶点k的加入，对closest数组进行更新
        for(int j=1;j<=G.vexnum;j++)
        {
            if(closest[j].tag==false&&G.arcs[k][j]<closest[j].lowcost)
            {
                //不在树上的顶点到新加入树上的顶点k的距离比原来小
                closest[j].lowcost=G.arcs[k][j];
                closest[j].vexcode=k;
            }
        }
    }
}